Computing systems often have various limitations on system resources. For example, a multi-processor computer system may have a large, but finite, number of central processing units (CPUs). Processes executing on the computer system may compete for the system resources. Accordingly, it is often desirable to efficiently allocate the system resources among executable processes running on the system.
Various scheduling algorithms have been developed to allocate system resources. For example, a simple scheduling algorithm is the first-come, first-served algorithm, wherein processes requiring a resource are allowed to access that resource in the order in which they have requested it. When the importance or priority of the processes is not all equal, the first-come, first-served algorithm can provide a relatively poor solution. Better performance can be obtained in some situations using priority schemes, such as preemptive scheduling.
As the constraints placed upon the scheduling problem become more complex, obtaining an efficient solution becomes difficult. One particular complication is when there are multiple processes which can be assigned to multiple resources and/or processors. The addition of constraints, such as minimum resource allocations or maximum resource allocations on a per process basis adds even more complexity to the scheduling problem. Optimal solutions to such a multi-dimensional problem can take a considerable amount of computation to solve.